﻿//将一个给定字符串 s 根据给定的行数 numRows ，以从上往下、从左到右进行 Z 字形排列。
//比如输入字符串为 "PAYPALISHIRING" 行数为 3 时，排列如下：
//P   A   H   N
//A P L S I I G
//Y   I   R
//之后，你的输出需要从左往右逐行读取，产生出一个新的字符串，比如："PAHNAPLSIIGYIR"。
//请你实现这个将字符串进行指定行数变换的函数：
//string convert(string s, int numRows);
//
//输入：s = "PAYPALISHIRING", numRows = 3
//输出："PAHNAPLSIIGYIR"
//
//输入：s = "PAYPALISHIRING", numRows = 4
//输出："PINALSIGYAHRPI"
//解释：
//P     I    N
//A   L S  I G
//Y A   H R
//P     I
//
//输入：s = "A", numRows = 1
//输出："A"
//
//提示：
//	1 <= s.length <= 1000
//	s 由英文字母（小写和大写）、',' 和 '.' 组成
//	1 <= numRows <= 1000

class Solution {
public:
    string convert(string s, int numRows) {
        // 处理边界情况

        if (numRows == 1)
            return s;

        string ret;
        int d = 2 * numRows - 2, n = s.size();

        // 1.先处理第⼀⾏

        for (int i = 0; i < n; i += d)
            ret += s[i];

        // 2.处理中间⾏

        for (int k = 1; k < numRows - 1; k++) // 枚举每⼀⾏

        {
            for (int i = k, j = d - k; i < n || j < n; i += d, j += d) {
                if (i < n)
                    ret += s[i];
                if (j < n)
                    ret += s[j];
            }
        }

        // 3.处理最后⼀⾏

        for (int i = numRows - 1; i < n; i += d)
            ret += s[i];
        return ret;
    }
};